package com.cy.letcode.number.最长回文子串;


/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ForceSolution {

    public static void main(String[] args) {
        System.out.println(new ForceSolution().longestPalindrome("abab"));
    }


    /**
     * 暴力匹配算法
     *
     * @param s 目标串
     * @return 回文子串
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        //最大长度为1，至少有一个字符
        int maxLength = 1;
        int begin = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i++) {
            for (int j = len - 1; j > i; j--) {
                System.out.println(s.substring(i, j + 1));
                if (j - i + 1 > maxLength && validPalindrome(chars, i, j)) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLength);
    }

    /**
     * 验证是否是回文数组
     *
     * @param chars 字符串数据
     * @param left  左边的偏移量
     * @param right 右边的偏移量
     * @return 是否是回文传
     */
    public boolean validPalindrome(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left] != chars[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


}